#define _CRT_SECURE_NO_WARNINGS   1
#include<stdio.h>
//int main()
//{
//	char* words[5] = { 0 };
//	for (int i = 0; i < 5; i++)
//	{
//
//		scanf("%s",words[i]);
//		printf("\n");
//		printf("\n");
//		printf("%s", words[i]);
//		printf("\n");
//	}
//	
//
//	return 0;
//}

#include <stdio.h>
#include <math.h>

int IsP(int j)
{
    int flag = 1;
    for (int i = 2; i <= sqrt(j); i++)
    {
        if (j % i == 0)
        {
            flag = 0;
            return 0;
        }
    }
    return 1;
}

int FindP(long long n, int* Parr)
{
    int a = 0;
    for (int j = 2; j <= n; j++)
    {
        if (n % j == 0 && IsP(j) == 1)
        {
            Parr[a] = j;
            a++;
        }
    }
    return a;
}

int Find_t(int Parr, long long n)
{
    int tmp = Parr;
    int t = 0;
    while (n % tmp == 0)
    {
        n /= tmp;
        t++;
    }
    return t;
}

int IsSave(int k, int* tarr, int length)
{
    for (int i = 0; i < length; i++)
    {
        if (k <= tarr[i])
        {
            return i + 1;
        }
    }
    return 0;
}

int main()
{
    int q = 0;
    int k = 0;
    long long n = 0;
    scanf("%d", &q);

    while (q > 0)
    {
        scanf("%lld %d", &n, &k);
        int* Parr = (int*)malloc((n + 1) * sizeof(int));
        int a = FindP(n, Parr);

        int* tarr = (int*)malloc(a * sizeof(int));
        for (int i = 0; i < a; i++)
        {
            tarr[i] = Find_t(Parr[i], n);
        }
        int m = IsSave(k, tarr, a);
        if (m == 0)
        {
            printf("%d\n", 1);
        }
        else
        {
            long long s = 1;
            for (int i = 0; i < m; i++)
            {
                int x = Parr[i];
                int y = tarr[i];
                s *= pow(x, y);
            }
            printf("%lld\n", s);
        }
        free(Parr);
        free(tarr);
        q--;
    }

    return 0;
}